/*
 * File:   connected_components.c
 * Author: aishwarya
 *
 * Created on March 12, 2011, 11:08 AM
 * (Greedy) Algorithm (using Disjoint Sets) to find Connected Components of a Graph.
 * Similiar to Kruskal's MST finding algorithm.
 */

#include "graph_algos.h"
#include "../DataStructures/avdtech.h"
#include "../DataStructures/disjoint_sets.h"

void connected_components(GRAPH *g, void (*userfn)(disjoint_sets *s)) {
    int i, total = 0, nedge_pairs;
    Parent x, y;
    EDGE_PAIR *epair;
    disjoint_sets s;

    set_init(&s, g->nvertices);

    epair = (EDGE_PAIR *) malloc(g->nedges * sizeof (EDGE_PAIR));
    nedge_pairs = graph_create_edge_pairs(g, epair);

    for (i = 0; i < nedge_pairs; i++) {
        x = set_find(&s, epair[i].u);
        y = set_find(&s, epair[i].v);
        if (x != y) {
            set_union_p(&s, x, y);
            total++;
            if (total == g->nvertices - 1)
                break;
        }
    }

    userfn(&s);
    set_clean(&s);
    free(epair);
}

/*
int maxcount;
void ans(disjoint_sets *s) {
    int i, *max, k;

    max = (int *) calloc(s->nelements + 1, sizeof (int));

    for (i = 1; i <= s->nelements; i++)
        max[set_find(s, i)]++;

    for (maxcount = 0, i = 1; i <= s->nelements; i++)
        if (max[i])
            maxcount++;

    free(max);
}

int main() {
    GRAPH g;
    connected_components(&g, ans);
}
*/
